#pragma once
#include<iostream>
using namespace std;
template<class K>
struct BSTNode
{
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;

    BSTNode(const K& key)
        :_key(key)
        , _left(nullptr)
        , _right(nullptr)
    {
    }
};
template<class K>
class BSTree {
    typedef BSTNode<K> Node;
public:
    bool Insert(const K& key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else return false;
        }
        cur = new Node(key);
        if (parent->_key > key) parent->_left = cur;
        else parent->_right = cur;
        return true;
    }
    bool find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (key > cur->_key) cur = cur->_right;
            else if (key < cur->_key) cur = cur->_left;
            else return true;
        }
        return false;
    }
    bool erase(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }

            else if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                if (cur->_left == nullptr)
                {
                    if (_root != cur)
                    {
                        if (cur == parent->_left)
                        {
                            parent->_left = cur->_right;
                        }
                        else
                        {
                            parent->_right = cur->_right;
                        }
                    }
                    else
                    {
                        _root = cur->_right;
                    }
                    delete cur;
                }
                else if (cur->_right == nullptr)
                {
                    if (_root != cur)
                    {
                        if (cur == parent->_left)
                        {
                            parent->_left = cur->_left;
                        }
                        else
                        {
                            parent->_right = cur->_left;
                        }
                    }
                    else
                    {
                        _root = cur->_left;
                    }
                    delete cur;
                }
                else
                {
                    Node* minrightparent = cur;
                    Node* minright = cur->_right;
                    while (minright->_left)
                    {
                        minrightparent = minright;
                        minright = minright->_left;
                    }
                    swap(minright->_key, cur->_key);
                    if (minrightparent->_right == minright) minrightparent->_right = minright->_right;
                    else minrightparent->_left = minright->_right;
                    delete minright;
                }
                return true;
            }
        }
        return false;
    }
    void Inorder()
    {
        _Inorder(_root);
        cout << endl;
    }
private:
    void _Inorder(Node* root)
    {
        if (root == nullptr) return;
        _Inorder(root->_left);
        cout << root->_key << " ";
        _Inorder(root->_right);
    }
    Node* _root = nullptr;
};